|
| creator |
Staiger-Stöhr, Stefan
| | date |
2009-02-13
| | | | description |
33 pages
| |
Andersen's analysis is the most influential pointer analysis
known so far. This paper, which contains parts of the author's
upcoming PhD thesis, for the first time presents a flow-sensitive
version of that analysis. We prove that the flow-sensitive version
still has the same cubic complexity. Thus, the higher precision
comes without loss of asymptotic scalability. This contradicts
common wisdom of flow-sensitivity being substantially more
expensive.
Compared to other flow-sensitive pointer analyses, we have no
expensive data-flow problem on the CFG. Instead, we simply propagate
pointer targets along data-flow relations which we determine during
the analysis. Our analysis in fact combines the computation of the
interprocedural SSA data-flow representation and the uncovering of
pointer targets. It also integrates the computation of control-flow
relations. The analysis thus presents a new, sparse approach for the
flow-sensitive solution of the central problems for data-flow based
program analyses.
This paper also presents two extensions for higher precision. The
first extension shows how the analysis can detect strong updates
without increasing the complexity. The second extension describes a
context-sensitive version which excludes unrealizable paths.
Together this yields the first analysis of that precision which only
has a complexity of n^4. This is a substantial improvement over the
previous n^6 bound found by Landi.
Thus, in summary this report describes several theoretical advances
in the field of flow-sensitive pointer analysis. It also provides
details on the algorithms used for incremental SSA construction and
context-sensitive pointer propagation.
| | format |
application/pdf
| | 289396 Bytes | |